package com.gxc.array;

/**
 * 给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k。
 * 求 arr 的所有子 数组中所有元素相加和为 k 的最长子数组长度。
 * 例如，arr=[1,2,1,1,1]，k=3。
 * 累加和为 3的最长子数组为[1,1,1]，所以结果返回 3。
 * 要求:时间复杂度0(N)，额外空间复杂度0(1)
 *
 * 解法：
 * 滑动窗口
 */
public class MostEldestArray {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,1,1,1};
        int aim = 3;

        System.out.println(process(arr, aim));
    }

    public static int process(int[] arr, int aim) {
        if (arr == null || arr.length == 0) return 0;

        //窗口左右位置
        int l = 0;
        int r = 0;
        int sum = 0;
        int max = 0;

        while (r < arr.length) {
            sum += arr[r];
            if (sum < aim) {
                r++;
            } else if (sum == aim) {
                max = Math.max(max, r-l+1);
                r++;
            } else {
                //右窗口滑动时，需要减去右窗口的数值
                sum -= arr[l];
                sum -= arr[r];
                l++;
            }
        }
        return max;
    }
}
